import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/31 15:33
 * @description 归并排序，每一行都是一个有序数组，问题转换为从n个有序数组中找到第k大的数
 */
public class Solution3 {
    public static void main(String[] args) {
        Solution3 solution3 = new Solution3();
        int[][] matrix = {{1, 5, 9}, {10, 11, 13}, {12, 13, 15}};
        solution3.kthSmallest(matrix, 8);
    }

    public int kthSmallest(int[][] matrix, int k) {
        // 小根堆，每次弹出最小的，
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            // 第一列为全局最小的值。
            pq.offer(new int[]{matrix[i][0], i, 0});
        }
        for (int i = 0; i < k - 1; i++) {
            int[] now = pq.poll();
            if (now[2] != n - 1) {
                // 没有到达边界，下一个候选人为这个数所在行的下一个，
                pq.offer(new int[]{matrix[now[1]][now[2] + 1], now[1], now[2] + 1});
            }
        }
        return pq.poll()[0];
    }
}
